This invention relates to fingerprint matching systems, and possibly to systems for the matching of personal characteristics other than fingerprints, and more particularly, to matching systems, e.g. FBI/AFIS (Federal Bureau of Investigation/Automated Fingerprint Identification System) systems in which a fingerprint or other personal characteristic is to be matched to reference or file fingerprints or characteristics in a database by a prescreen ARGMatch(trademark) (Attributed Rotational Graph) identification algorithm of the FBI/AFIS program.
Pattern matching or comparison schemes have many applications, such as identifying machine parts in a manufacturing context, and the reading of addresses in a mail sorting context. The above-mentioned applications are among the simpler uses of such comparison schemes, because in the case of machine parts, the number of different parts is finite, and their shapes are in general fairly simple; the text reading context has only twenty-six letters and ten numbers to identify, although the number of permutations of text is large.
More complex types of comparisons are those involving differentiation among items which are similar, but not identical. This is especially so when the conditions under which the images are formed are not uniform. When the images are of biological specimens, the variability of the images may be substantial. One such aspect of image matching is that of matching the retinal patterns of subjects for identification. Another use is that of matching fingerprints for comparison with file fingerprints.
Fingerprints are very rich in information content. There are two major types of information in a fingerprint. First is the ridge flow information, and second are the specific features or xe2x80x9cminutiaxe2x80x9d of the fingerprint. As used herein, the term xe2x80x9cminutiaxe2x80x9d is used to denote both the singular and plural. Fingerprints uniquely identify an individual based upon their information content. Information is represented in a fingerprint by the minutia and their relative topological relationships. The number of minutia in a fingerprint varies from one finger to another, but, on average, there are about eighty (80) to one hundred and fifty (150) minutia per fingerprint. In the fingerprint context, a large store of file fingerprints exists in law enforcement offices around the country. These file fingerprints include fingerprints of known individuals, made in conjunction with their apprehension or for some other reason such as a security clearance investigation or of obtaining immigration papers, often by rolling the inked fingers on cards, and also includes copies of latent fingerprints extracted from crime scenes by various methods.
These file or reference fingerprints are subject to imperfections such as overinking, which tends to fill in valleys in fingerprints, and underinking, which tends to create false ridge endings, and possibly overinking and underinking in different regions of the same fingerprint image. Smudges and smears can also occur at different places in the fingerprint due to unwanted movement of the finger, or uneven pressure placed on the finger during the rolling process. The stored file fingerprints are also subject to deterioration while in storage, which may occur, for instance, due to fading of the older images or due to stains. Moreover, the wide variation in the level of experience among fingerprint operators, and the conditions under which the fingerprints are obtained, produce a wide variation in quality of the fingerprint images. Similar effects occur due to variation of the scanning devices in cases of live scanning of fingerprints.
Matching of fingerprints in most existing systems relies for the most part upon comparison of cores and deltas as global registrations points. This tends to render such comparisons susceptible to errors due to the many sources of distortion and variations mentioned above, which almost always occur due to the various different inking, storage and preprocessing conditions which may be encountered.
As described at pages 164-191 of the text ADVANCES IN FINGERPRINT TECHNOLOGY, by Henry C. Lee and R. E. Guenssten, published by L. Elsevier in 1991, efforts have been underway for a long time to automate fingerprint identification. This is because manual searching is no longer feasible due to the large number of reference files. The effort to automate fingerprint identification involves two distinct areas. The first is that of fingerprint scanning and minutia identification, and the second is a comparison of lists of minutia relating to different fingerprints in order to identify those which match. Large files of reference or file fingerprints have been scanned, and minutia lists in digital form obtained therefrom, either by wholly automated equipment, or by semiautomated equipment requiring human assistance. While not all problems in scanning of fingerprints and detection of minutia have been solved, it appears that the matching problem is the more pressing at this point in the evolution of the technology.
The matching or search subsystem constitutes the most critical component of any Automated Fingerprint Identification System (AFIS). Its performance establishes the overall system matching reliability (the probability of declaring a correct match, if one exists in the database), match selectivity (the average number of false candidates declared in each search attempt), and throughput, which is particularly important in large database systems. The unique identification of fingerprints is usually performed using the set of minutia contained in each fingerprint. For each fingerprint, these minutia form a minutia map.
For example, U.S. Pat. No. 5,613,014, issued Mar. 18, 1997 in the name of Eshera et al, describes a fingerprint matching technique using a graphical Attribute Relational Graph (ARG) approach. This ARG approach is fast, and particularly advantageous for those cases in which the minutia of the unknown or search fingerprint are numerous and well defined, but may be hindered in finding the correct match by errors in locating minutia near the center of each star in the fingerprint when the latent image is poor and minutia are missing.
U.S. Pat. No. 5,933,516, issued Aug. 3, 1999 to Tu et al, discloses a fingerprint matching method by an estimation of a maximum clique. During operation, a base pair of minutia is selected in the unknown or search fingerprint under consideration and each reference or file fingerprint. For each base pair selected for comparison, those sets of minutia pairs are selected which satisfy a priori constraints including angle, distance and ridge counts, to generate a first set of minutia which support the fingerprints correspondence. A second set of supporting minutia pairs is generated from the first set which doesn""t contain pairs which are inconsistent with the base pair bias angle. A third set is established using xe2x80x9cdynamic programmingxe2x80x9d to determine the largest topologically self-consistent subset of the second set. The minutia pairings are counted in the third set to establish the merit of the base pair.
For each of the minutia of the unknown or search fingerprint, a correspondence group is generated of a predetermined number of minutia of the reference or file fingerprint which have the greatest merit. The correspondence group is searched for a maximal clique in which every search reference fingerprint minutia pair is consistent with every other minutia pair in the clique. A cardinality equal to the number of search reference fingerprint minutia pairs in the maximal clique is stored. The steps are then repeated to generate a set of cardinalities.
In those cases in which the search print quality or other considerations result in failure to perfectly match by the ARG method, it may be desirable to perform a match using a larger number of constraints than in the ARG technique.
Comparing a fingerprint image obtained in any fashion, from inked rollings to live scan, with a large repository of similarly obtained fingerprint images is a task best accomplished through a cascaded series of processing proceeding from course to fine grain matchings. Speed of execution is a necessary component of the process. To that end, a prescreen filtering algorithm based upon an ARG matching algorithm, e.g., the ARGMatch(trademark) identification algorithm of the FBI/AFIS program, would be a significant contribution to the state of the art of automated fingerprint identification.
To that end, the present invention provides a prescreen filtering method and algorithm based upon an ARG matching method and algorithm, e.g. the ARGMatch(trademark) identification method and algorithm of the FBI/AFIS program, and provides several significant differences from conventional approaches. Attributed Relational Graph (ARG) techniques are employed in a node-by-node matching to individually determine a best alignment of the minutia of the search and file fingerprints. The approach is preferably a software implementation (versus a hardware implementation), lending itself to ease of implementation in any number of architectures, as well as ease of upgrades when speed and reliability improvements are realized.
For each minutia (termed a central minutia in the explanation below) of a fingerprint that is characterized in both a search fingerprint and a reference file fingerprint in a reference file, a set of minutia neighbors is determined for that central minutia based upon its directional component. The space about each central minutia is divided into four quadrants, with the first quadrant being centered about the directional component of the central minutia, and the second, third and fourth quadrants being spaced every 90xc2x0 in a counterclockwise direction from the first quadrant. The closest minutia in each of the four quadrants is determined to be the minutia neighbor in that quadrant for each central minutia. In alternative embodiments, other types of coordinate systems and quadrants can be employed, such as a clockwise spacing of quadrants, a different number of quadrants, or a polar coordinate system.
Let U be a set of minutia for a search fingerprint and V be a set of minutia for a reference or file fingerprint. The Distance Matrix (DM) ARGMatch(trademark) identification method and algorithm of the FBI/AFIS system, modified for quadrant neighbor processing, generates a Distance Matrix (DM) score for each and every different pair of minutia [u,v] in the two different sets of minutia U, V.
First, the directional components of each and every different pair of minutia from the two sets are compared to ensure that they are within a given angular tolerance, which is selected to allow for a reasonable variation in rotational alignments which are a result of the different fingerprint collection and imaging processes, but does not allow a pair of minutia from completely different ridge flows to be compared.
After this directional alignment tolerance criteria has been passed, a Distance Matrix (DM) score is generated for each passed [u,v] minutia pair by performing a virtual alignment of the [u,v] minutia pair in location and direction, and then by comparing the distances and relative orientations between each of the four pairs of minutia neighbors in each of the four quadrants, which represents how well each different [u,v] minutia pair match each other.
For a minutia pair [u,v], if the maximum DM score for [u,vj] (i.e., a single search minutia u compared with all of the file minutia) occurs at v, and similarly the maximum DM score for [ui, v] (i.e., a single file minutia v compared with all of the search minutia) occurs at u, then this minutia pair [u,v] is considered to be well matched . In order to prevent the pairing of poorly aligned minutia, a minimum DM score must be obtained in order for the minutia pair to be considered well matched.
A set of well matched minutia pairs forms the basis for the prescreen function of the present invention. The size of this set of well matched minutia pairs, relative to the sizes of other sets of well matched minutia pairs for all other file fingerprints in the repository file, determines if a particular file fingerprint is passed along to the more complete and rigorous matching functions of an Automated Fingerprint Identification System (AFIS), in a manner as disclosed in U.S. Pat. Nos. 5,613,014 and 5,933,516.
A final consistency check is performed on this set of well matched minutia pairs. The difference of each minutia pair""s directional components (a virtual rotational transformation) is computed and placed into a histogram. Following a smoothing process, the maximum value in the histogram indicates the most likely rotational transformation for a matching of this set of well matched minutia pairs. Using the most likely rotational transformation, the difference of each minutia pair""s directional components of the set of well-matched minutia pairs is now recomputed, and any minutia pair exhibiting a directional difference greater than a given tolerance is removed from further consideration, to derive a final set of well-matched minutia pairs.
The size of this final set of well matched minutia pairs is the prescreen function or metric for a particular search-file pair of fingerprints. In general, the prescreen function passes along a top percentage of the number of file fingerprints forming the repository file for further AFIS processing. The size of this final set of well matched minutia pairs is the metric or criteria that is used in determining the top percentage.